# # -*- coding:utf-8
# 5179. 将二叉搜索树变平衡 显示英文描述
# 用户通过次数60
# 用户尝试次数60
# 通过次数60
# 提交次数66
# 题目难度Medium
# 给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。
#
# 如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。
#
# 如果有多种构造方法，请你返回任意一种。

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def __init__(self):
        self._data = []

    def dfs(self,node:TreeNode):
        # if node is not None:

        if node.left is not None:
            self.dfs(node.left)
        self._data.append(node.val)
        if node.right is not None:
            self.dfs(node.right)

    def buildTree(self,l,r):
        if l>r:
            return None
        node = TreeNode()
        mid = (l+r)//2
        node.val = self._data[mid]
        node.left = self.buildTree(l,mid-1)
        node.right = self.buildTree(mid+1,r)
        return node



    def balanceBST(self, root: TreeNode) -> TreeNode:
        self.dfs(root)
        print(self._data)
            # resBack = TreeNode(self._data.pop())
            #
            # qqqqq= [resBack]
            # while self._data.__len__()>0:
            #     curNode = qqqqq.pop(-1)
            #     lNode = TreeNode(self._data.pop(-1))
            #     curNode.left = lNode
            #
            #     if self._data.__len__()>0:
            #         rNode = TreeNode(self._data.pop(-1))
            #         curNode.right = rNode
            #
            #     qqqqq.append(lNode)
            #     qqqqq.append(rNode)

        return self.buildTree(0,self._data.__len__()-1)











